The present invention relates to a logic circuit using pass transistors, and more particularly to a logic circuit with a combination of one or more pass transistors and one or more multiple-input logic gates. Further, the present invention relates to a method of designing a logic circuit for executing a desired logical operation, using a small number of transistors and a small number of stages in a form in which the advantages of pass transistors and multiple-input logic gates are utilized. The present invention also relates to a logic circuit using pass transistors, capable of executing a logical operation in an efficient manner, and to a system using such a logic circuit. The present invention also relates to a method of executing a logical operation in an efficient fashion using a logical circuit including pass transistors.
It is known in the art to employ a xe2x80x9cpass-transistor logic circuitxe2x80x9d to reduce a number of elements and power consumption, and to improve operating speed. Pass-transistor logic circuits use pass transistors each comprising a switching device. Conduction between an input terminal and output terminal of the switching device is turned ON or OFF according to a potential at a control terminal. Each pass transistor is realized by connecting the switching device so that whether a logic signal applied to the input terminal is transmitted to the output terminal can be determined with the conducting or nonconducting state of each switching device. In general, a plurality of pass transistors are connected in series and/or parallel to constitute a pass-transistor logic circuit for executing a desired logical operation. As for the switching devices, MOS transistors, for example, may be used. In this case, the gate, source, and drain of each MOS transistor correspond to the control, input, and output terminals, respectively. Both n- and p-channel MOS transistors and the combination of the n- and p-channel MOS transistors may be used as the pass transistors. A pass transistor employing the combination of an n- and a p-channel MOS transistor is often called as a xe2x80x9ctransmission gatexe2x80x9d or a xe2x80x9ctransfer gatexe2x80x9d.
It is also known to realize a logic circuit using a combination of one or more transfer gates and a logic gate such as an inverter, multiple-input NOR gate, multiple-input NAND gate, etc.
The inventor of the present invention has proposed a composite pass-transistor logic circuits which is realized with a combination of a plurality of pass-transistor logic circuits (pass-transistor logic trees) and a multiple-input logic circuit as disclosed in the U. S. patent application Ser. No. 08/716,883 titled xe2x80x9cLOGIC CIRCUIT UTILIZING PASS TRANSISTORS AND LOGIC GATE,xe2x80x9d filed on Sep. 20, 1996, and in the U. S. patent application Ser. No. 08/763,264 titled xe2x80x9cSEMICONDUCTOR INTEGRATED CIRCUIT CAPABLE OF REALIZING LOGIC FUNCTIONS,xe2x80x9d filed on Dec. 10, 1996. These patent applications cited above are incorporated herein by reference.
However, a practical technique of designing integrated circuits, in which various functions required by various users are realized using a logic circuit including pass transistors, has not been established. For example, in the technique disclosed in Japanese Unexamined Patent Publication No. 1-216622, logic circuits each composed of a combination of transfer gates and a logic gate are prepared as logic cells, and a desired LSI is designed by combining these logic cells. However, a specific technique is not disclosed for designing various logic circuits required for practical applications, although some simple logic circuits such as an exclusive OR, exclusive NOR, and full adder are disclosed.
One known technique of designing pass-transistor logic circuits is to use a BDD (binary decision diagram). For example, a logical expression (1) which includes variables a, b, and c as described below can be represented in a BDD as shown in FIG. 1. This BDD can then be mapped to a pass-transistor logic circuit as shown in FIG. 2. Herein, a process of replacing a logical expression by a corresponding logic circuit is referred to as a mapping. Symbol ⊕ denotes exclusive OR in the logical expression (1).
f=a⊕b⊕cxe2x80x83xe2x80x83(1)
When equivalent logical expressions are represented by BDDs, the size of the graph varies depending on the order of variables included in the equivalent logical expressions. For example, the logic circuit shown in FIG. 3 and the logic circuit shown in FIG. 5 are equivalent to each other although there is a difference in the order of variables. The logic circuit shown in FIG. 3 can be represented by a BDD graph as shown in FIG. 4, and the logic circuit shown in FIG. 5 can be represented by a BDD graph as shown in FIG. 6. The logic circuit shown in FIG. 3 and the corresponding BDD graph shown in FIG. 4 is the optimum in terms of the order of variables. In contrast, the logic circuit shown in FIG. 5 and the corresponding BDD graph shown in FIG. 6 is the worst in the order of variables.
If the number of inputs of a logical operation, that is the number of variables included in a logical expression, is given by n, then, in theory, there can be at most 2n different orders of variables. It is practically impossible to select an optimum order from such a huge number of possible orders of variables, because the process of selecting the optimum order will take a very long time. On the other hand, if the processing time required to determine the order of variables is limited, there is a risk that the resultant order of variables be inadequate and very far from the optimum order, which will cause an impractically great increase in the number of gates making up a logic circuit mapped from the inadequate BDD graph.
There are various techniques known to determine the order of variables in a BDD. For example, in a technique disclosed in a paper titled xe2x80x9cMethod of determining the order of variables with respect to the xe2x80x9cwidthxe2x80x9d of a common binary decision diagramxe2x80x9d (Hata, The 42-th Meeting of Information Processing Society of Japan, 2J-5, 1991, hereinafter referred to as the first prior art), when a BDD is divided into two parts at a boundary between a k-th input variable and a (k+1)th input variable, the number of edges passing through the cross section is defined as the xe2x80x9cwidthxe2x80x9d. When variables are selected in the process of determining variables from the top to bottom, each variable is selected from input variables remaining as candidates so that each variable results in a minimum width. In this method, if the number of input variable is n and the number of nodes of the BDD is G, the calculation time required to determine the order of the input variables is of the order of O(n2xc2x7G), wherein O(n2xc2x7G) refers to a time required to perform n2xc2x7G times operations.
In another technique disclosed in a paper titled xe2x80x9cMulti-Level Pass-Transistor Logic for Low-Power ULSIsxe2x80x9d (Yano et al., IEEE 0-7803-3036-6/95, hereinafter the second prior art), those parts which share the same logic function are extracted from the original BDD, and the BDD is replaced by a new BDD so that the resultant BDD has the same number of leaves as that included in the original BDD. After that, logic associated with the control inputs at nodes in the resultant BDD is created so that the BDD represents the original logic.
In the first prior art, however, the BDD has a feature that AND and/or OR logic circuits are connected in series by pass transistors, and thus a great number of pass-transistor stages are required in the logic circuit. To determine the order of input variables within a practical calculation time, the number of input variables should be limited to a few tens and the number of nodes should be limited to a few ten thousands. Furthermore, the solution of the order of input variables obtained by the above calculation is still far from the optimum solution.
In the second prior art, it is possible to map a logical expression into a pass-transistor logic circuit having a less number of pass-transistor stages. However, a buffer is needed to be provided at a control input of each pass transistor, and no reduction in the number of transistors is achieved. Furthermore, the degree of freedom is too large in the process of replacing parts which have a common logic by a new BDD. Therefore, this technique is not suitable for use in designing a large scale integrated circuit with a CAD (computer aided design) system.
In both the first and second conventional techniques, a desired logic circuit is realized using usual pass-transistor logic circuits including a plurality of stages of multiplexers constructed of pass transistors. Therefore, these techniques are unsuitable for use in designing a logic circuit composed of both pass transistors and one or more multiple-input logic gates. That is, it is impossible to construct a logic circuit with pass transistors and one or more multiple-input logic gates in an efficient fashion in which their advantages are utilized. If a logical expression is optimized according to the first or second prior art, and the result is mapped into a logical circuit including both pass transistors and multiple-input logic gates, the resultant logic circuit will include a great number of transistors and/or the circuit will include a great number of stages.
In view of the above problems in the conventional techniques, it is an object of the present invention to provide a design method and a CAD system for designing a logic circuit with pass transistors in such a manner that the total number of transistors and the number of stages are minimized. It is another object of the present invention to provide a logic circuit with pass transistor in which various logical operations can be realized in an efficient fashion, an electronic system using such a logic circuit, and a method of executing various logical operations in an efficient fashion.
According to an aspect of the present invention, there is provided a method of mapping a logical expression, which expresses logic to be realized by a logic circuit, to a specific form of a logic circuit in which pass transistor are used in an advantageous fashion, and there is also provided a method of designing a logic circuit including such a mapping process. Furthermore, there is also provided a CAD system for use in practicing such the methods.
According to another aspect of the present invention, there is provided a method of designing a logic circuit including a process of transforming a logical expression into an optimized form so as to make it easy to map the logical expression to a logic circuit in which pass transistor are used in an advantageous fashion. Furthermore, there is also provided a CAD system for use in practicing such the design method.
According to still another aspect of the present invention, there is provided a method of mapping a combinational logical expression to a logic circuit comprising a multiplexer composed of a combination of pass-transistors and inverting logic gates so that the logic circuit includes a small total number of transistors. Furthermore, there is also provided a CAD system for use in practicing such the method.
According to still another aspect of the present invention, there is provided a method of mapping product terms containing a various number of logic functions to a logic circuit comprising a combination of one or more multiple-input gates and an appropriate number of multiplexers so that the logic circuit includes a small total number of transistors and a small number of stages. There is also provided a CAD system for use in practicing such the method. Furthermore, there is provided a logic circuit for executing a logical operation expressed by a logical expression including product terms containing a various number of logic functions wherein the logic circuit includes a small total number of transistors and a small number of stages. There is also provided an electronic system using such a logic circuit. Furthermore, there is provided a method of efficiently executing a logical operation expressed by a logical expression including product terms containing a various number of logic functions.
According to another aspect of the present invention, there is provided a method of mapping a logical expression including a logic group containing a complementary variable to a logic circuit comprising a combination of one or more multiple-input gates and one or more multiplexers so that the logic circuit includes a small total number of transistors and a small number of stages. There is also provided a CAD system for use in practicing such the method. Furthermore, there is provided a logic circuit comprising a combination of one or more multiple-input gates and one or more multiplexers, for executing a logical operation expressed by a logical expression including a logic group containing a complementary variable wherein the logic circuit includes a small total number of transistors and small number of stages. There is also provided an electronic system using such a logic circuit. Furthermore, there is provided a method of efficiently executing a logical operation expressed by a logical expression including a logic group containing a complementary variable, using a logic circuit comprising a combination of one or more multiple-input gates and one or more multiplexers.
According to another aspect of the present invention, there is provided a method of mapping a logical expression including a logic group containing a complementary variable to a logic circuit comprising a combination of two types of multiple-input gates and one or more multiplexers so that the logic circuit includes a small total number of transistors and a small number of stages. There is also provided a CAD system for use in practicing such the method. Furthermore, there is provided a logic circuit comprising a combination of two types of multiple-input gates and one or more multiplexers, for executing a logical operation expressed by a logical expression including a logic group containing a complementary variable, wherein the logic circuit includes a small total number of transistors and a small number of stages. There is also provided an electronic system using such a logic circuit. Furthermore, there is provided a method of efficiently executing a logical operation expressed by a logical expression including a logic group containing a complementary variable, using a logic circuit comprising a combination of two types of multiple-input gates and one or more multiplexers.
According to an aspect of the present invention, there is provided a method of designing a logic circuit for mapping a logical expression, comprising: identifying a first logic group including a first plurality of logic functions and at least one complementary variable shared by the first plurality of logic functions in the logical expression; and mapping the logical expression, including: placing a multiplexer having input terminals, at least one control terminal and an output terminal in the logic circuit; and connecting the input terminals and the at least one control terminal of the multiplexer to input the first plurality of logic functions and the at least one complementary variable so that the first logic group is output from the output terminal of the multiplexer.
Preferably, the identifying step further identifies a second logic group having a second plurality of logic function and a common variable shared by the second plurality of logic functions in the logical expression; and the mapping further includes: placing a multiple-input logic gate having input terminals and an output terminal in the logic circuit; and connecting the input terminals of the multiple-input logic gate to input the common variable and a sum of the second plurality of logic functions so that the second logic group is output from the output terminal of the multiple-input logic gate.
There is also provided a CAD system for designing a logic circuit for mapping a logical expression, the system comprising: means for identifying a first logic group including a first plurality of logic functions and at least one complementary variable shared by the first plurality of logic functions in the logical expression; and means for mapping the logical expression, including: means for placing a multiplexer having input terminals, at least one control terminal and an output terminal in the logic circuit; and means for connecting the input terminals and the at least one control terminal of the multiplexer to input the first plurality of logic functions and the at least one complementary variable so that the first logic group is output from the output terminal of the multiplexer.
There is further provided a method of designing a logic circuit for mapping a logical expression, comprising: placing a multiplexer having input terminals, at least one control terminal and an output terminal in the logic circuit; and connecting the input terminals and the at least one control terminal of the multiplexer to input a first plurality of logic functions and at least one complementary variable so that a first logic group of the logical expression including the first plurality of logic functions and the at least one complementary variable shared by the first plurality of logic functions is output from the output terminal of the multiplexer.
To obtain a high-performance logic circuit with a small number of transistors, capable of operating at a high speed with small power consumption, it is desirable to map a given logical expression to a logic circuit in such a manner that a logic group in the logical expression having a form suited to be mapped using pass transistors be mapped using pass transistors.
For example, in the case of a logic group in the form expressed by a logical expression axc2x7C+{overscore (a)}xc2x7E (where C and E are arbitrary logic functions, xc2x7 denotes AND operation, and + denotes OR operation) which is a sum of product terms including a variable a in a complementary fashion, that is, one product term includes variable a in the non-inverted (positive-logic) form and the other product term includes variable a in the inverted (negative-logic) form, the logic group can be mapped in an efficient fashion to a logic circuit having a 2-input 1-stage multiplexer constructed with two pass transistors whose output terminals are connected to each other (herein referred to as a xe2x80x9cunit multiplexerxe2x80x9d). More specifically, the variable a (a signal corresponding to the variable a) is input to the control terminal of the multiplexer, and the logic functions C and E (signals corresponding to the logic functions C and E) sharing the variable a are input to the two input terminals, respectively, of the multiplexer so that the logic group (a signal corresponding to the logic group) is output at the output terminal of the multiplexer. Hereinafter, variables such as a described above are referred to as xe2x80x9ccomplementary variablesxe2x80x9d. If a logic group including a complementary variable is mapped to a multiplexer constructed with pass transistors in the above-described manner, the total number of transistors used and the power consumption are reduced compared to the case where the logic group is mapped using for example multiple-input logic gates.
In the above logical expression, lower-case characters such as a denote variables and upper-case characters such as C and E denote logic functions. The logic functions may be either a simple function only including a single variable or a complex function expressed by products and/or sums of a great number of variables. Furthermore, terms represented by products of a plurality of variables or logic functions such as axc2x7C and {overscore (a)}xc2x7E in the above logical expression are referred to as product terms. In the case where C and E are simple variables, the above-described product terms are simple product terms having a plurality of variables. Conversely, all elements of a product term may be logic functions (other than simple variables).
As another example, let us consider a logic group such as axc2x7bxc2x7C+axc2x7{overscore (b)}xc2x7D+{overscore (a)}xc2x7bxc2x7E+{overscore (a)}xc2x7{overscore (b)}xc2x7F (where C, D, E and F are arbitrary logic functions) including a sum of product terms each including two variables in a complementary fashion, that is, each product term includes either one of four possible combinations of two variables wherein each variable is in either the positive-logic form or the negative-logic form. In this case, the logic group can be mapped in an efficient fashion to a logic circuit using a 2-stage multiplexer including three unit multiplexers wherein the output terminals of two first-stage unit multiplexers are connected to the input terminals, respectively, of a second-stage unit multiplexer. In this specific example, variables a and b in the logical expression are complementary variables, and these variables are input to the control terminals of the multiplexer. More specifically, mapping may be performed in such a manner that the logic functions C, D, E and F are input to the four input terminals, respectively, of the two first-stage unit multiplexers each having two input terminals, variable b is input to the control terminal of each of the two first-stage unit multiplexer, and variable a is input to the control terminal of the second-stage unit multiplexer. Complementary variables of a logic group which can be mapped in an efficient fashion using a two- or more-stage multiplexer as in the above example are referred to as multiple-complementary variables. As can be understood from the above description, a logic group including a multiple-complementary variable can be mapped in an efficient fashion to a logic circuit using a multi-stage multiplexer including a less total number of transistors and a less number of stages.
A logical group expressed by a logical expression having a sum of three combinations of possible four combinations of two variables in the positive- and negative-logic forms, such as axc2x7bxc2x7C+axc2x7{overscore (b)}xc2x7D+{overscore (a)}xc2x7bxc2x7E may also be mapped in an efficient fashion using a 2-stage multiplexer. Also in this case, variables a and b act as multiple-complementary variables.
Furthermore, a logical expression including three or more multiple-complementary variables can be mapped using a three- or more-stage multiplexer. In practice, however, a limited number of pass transistors can be connected in series and thus there is a limit in the number of stages which can be included in a multiplexer.
In the case where a logic circuit is designed using both pass transistors and a multiple-input logic gate, it is desirable that a multiple-input logic gate be used in the mapping for a particular part, which is suitable for mapping using a multiple-input logic gate, of the logical expression to be realized by that logic circuit. For example, a simple NAND logic including a plurality of variables can be mapped in a preferable fashion using a multiple-input logic gate. A variable which is included in common in a plurality of product terms (hereinafter such a variable will be referred to as a xe2x80x9ccommon variablexe2x80x9d) can be mapped using in common a multiple-input logic gate in a more preferable fashion than can be achieved when the respective product terms are mapped individually using different multiple-input logic gates. The use of the common multiple-input logic prevents dispersion of AND or NAND terms. As a result, the logic can be realized with a reduced number of transistors. Furthermore, because the common variable can be input in a parallel fashion to the multiple-input logic gate, the number of stages of the logic circuit is reduced.
For example, in the case of a logic group in the form expressed by a logical expression axc2x7C+axc2x7D=axc2x7(C+D) including product terms containing a variable a in common, logic functions C and D share the common variable a. In this case, the logic group can be mapped in an efficient fashion such that variable a is input to one of the input terminals of an AND gate, and a sum of the logic functions C and D, which is obtained by properly mapping these logic functions, is input to the other input terminal of the AND gate. In the case where logic level adjustment which will be described later is made, a NAND gate or a NOR gate may be employed as a multiple-input logic gate for mapping a logic including a common variable.
More specifically, in the case where axc2x7bxc2x7cxc2x7d, axc2x7bxc2x7cxc2x7e, {overscore (a)}xc2x7{overscore (b)}xc2x7{overscore (c)}xc2x7f, and axc2x7{overscore (b)}xc2x7g are given as product terms, variables a, b, and c in a grouped product terms axc2x7bxc2x7cxc2x7(d+e) and a variable {overscore (b)} in a grouped product terms {overscore (b)}xc2x7({overscore (a)}xc2x7{overscore (c)}xc2x7f+axc2x7g) are common variables. In this case, axc2x7bxc2x7c and (d+e) are input to input terminals of one multiple-input logic gate, and {overscore (b)} and ({overscore (a)}xc2x7{overscore (c)}xc2x7f+axc2x7g) are input to input terminals of another multiple-input logic gate.
Furthermore, in the design of a logic circuit including pass transistors and a multiple-input logic gate, it is more preferable to simultaneously take into account the above two points. For example, it is preferable that a logic group including one or more complementary variables be mapped using a multiplexer composed of a combination of pass transistors, and that a logic group including one or more common variables be mapped using a multiple-input logic gate.
In practice, the above mapping process is performed in the process of designing a logic circuit using a CAD system including a CPU and a storage device. In a practical operation using the CAD system, the mapping process is performed by the CPU to generate electric information corresponding to the circuit and to store it at proper locations in the storage device. The above information is finally converted to a mask data after various procedures, and masks are produced according to the mask data. Using these masks, an actual circuit is realized in the form of a semiconductor integrated circuit. In the design process using the CAD system, in general, logic groups including complementary variables and/or logic groups including common variables are found (identified) in a logical expression to be realized by a logic circuit, before mapping the logic groups into the circuit using multiplexers and multiple-input logic gates. The above finding (identification) can be performed in various manners. For example, the process of optimizing a logical expression, as will be described in detail later, also includes a process for finding logic groups including complementary variables and/or logic groups including common variables.
According to another aspect of the present invention, there is provided a method of designing a logic circuit for mapping a logical expression, comprising: optimizing the logical expression including at least one cycle of a first procedure comprising: (a) selecting at least a part of the logical expression including a plurality of product terms each including plurality of variables; (b) identifying at least one complementary variable complementarily included in at least two of the product terms; and (c) grouping the at least two of the product terms by the at least one complementary variable to make a logic group including the at least one complementary variable and at least two logic functions sharing the at least one complementary variable; and mapping the optimized logical expression to the logic circuit.
Preferably, the optimizing further includes at least one cycle of a second procedure comprising: (a) selecting at least a part of the logical expression including a plurality of product terms each including a plurality of variables; (b) identifying a set of at least one common variable commonly included in at least two of the product terms; and (c) grouping the at least two of the product terms to make a second logic group including the at least one common variable and second logic functions sharing the at least one common variable.
There is also provided a CAD system for designing a logic circuit for mapping a logical expression, the system comprising: means for optimizing the logical expression including at least one cycle of a first procedure comprising: (a) selecting at least a part of the logical expression including a plurality of product terms each including plurality of variables; (b) identifying at least one complementary variable complementarily included in at least two of the product terms; and (c) grouping the at least two of the product terms by the at least one complementary variable to make a logic group including the at least one complementary variable and at least two logic functions sharing the at least one complementary variable; and means for mapping the optimized logical expression to the logic circuit.
There is further provided a method of designing a logic circuit for mapping a logical expression, comprising: optimizing the logical expression including at least one cycle of a procedure comprising: (a) selecting at least a part of the logical expression including a plurality of product terms each including a plurality of variables; (b) identifying a set of at least one common variable commonly included in at least two of the product terms; and (c) grouping the at least two of the product terms to make a logic group including the at least one common variable and logic functions sharing the at least one common variable; and mapping the optimized logical expression to the logic circuit including a multiplexer.
There is also provided a CAD system for designing a logic circuit for mapping a logical expression, the system comprising: means for optimizing the logical expression including at least one cycle of a procedure comprising: (a) selecting at least a part of the logical expression including a plurality of product terms each including a plurality of variables; (b) identifying a set of at least one common variable commonly included in at least two of the product terms; and (c) grouping the at least two of the product terms to make a logic group including the at least one common variable and logic functions sharing the at least one common variable; and means for mapping the optimized logical expression to the logic circuit including a multiplexer.
In order to design a logic circuit with pass transistors and a multiple-input logic gate used in an advantageous fashion, it is desirable to optimize, before mapping, a given logical expression representing a logical operation to be executed by the logic circuit so that the logical expression may be easily mapped to a specific form of the logic circuit in the advantageous fashion. The optimization may be performed using a CAD system.
The present invention provides a technique of making a logic group containing one or more complementary variables so as to make it easier to map the logical expression to a logic circuit in which a multiplexer is used in an advantageous fashion. The technique preferably makes a logic group containing multiple-complementary variables when it is possible. To the above end, the concept of the number of logical combinations of variables in product terms included in a logical expression is introduced.
As an example, in the case of a logical expression including product terms axc2x7bxc2x7c, axc2x7{overscore (b)}xc2x7d, {overscore (a)}xc2x7bxc2x7c and {overscore (a)}xc2x7{overscore (b)}xc2x7f, two variables a and b act as multiple-complementary variables. In this expression, the logical combinations of variables associated with the set of variables a and b are axc2x7b, axc2x7{overscore (b)}, {overscore (a)}xc2x7b, and {overscore (a)}xc2x7{overscore (b)}. Thus, in this example, the number of logical combinations of variables with respect to the set of variables a and b is four. While, the number of combinations between either variable a or b and any one of variables c, d, e, and f is one, and therefore any variable c, d, e, f cannot be a complementary variable. In a further example of a logical expression including product terms axc2x7bxc2x7c, axc2x7{overscore (b)}xc2x7d and {overscore (a)}xc2x7bxc2x7e in which two variables a and b act as multiple-complementary variables, the logical combinations with respect to variables a and b are axc2x7b, axc2x7{overscore (b)}, and {overscore (a)}xc2x7b, and thus the number of logical combinations with respect to the set of variables a and b is three.
As can be understood from the above discussion, a variable included in a set of variables which has a larger number of logical combinations has a possibility of being a complementary variable. Thus, one or more variables included in one or more set of variables having the largest number of logical combinations are the first candidates for identifying one or more complementary variables. Further, one or more variables included in one or more set of variables having the second largest number of combinations are the second candidates.
The number of logical combinations may change depending on a specific variable under consideration, when the number of combinations is determined with respect to the specific variable. For example, when axc2x7bxc2x7cxc2x7d, axc2x7bxc2x7cxc2x7e, {overscore (a)}xc2x7{overscore (b)}xc2x7{overscore (c)}xc2x7f, and axc2x7{overscore (b)}xc2x7g are given as product terms, logical combinations of a set of three variables a, b, and c are xe2x80x9ca, b, cxe2x80x9d and xe2x80x9c{overscore (a)}, {overscore (b)}, {overscore (c)}xe2x80x9d if all variables are equally treated. That is, the number of logical combinations is two. On the contrary, logical combinations of the same set of variables with respect to the variable a are xe2x80x9ca, b, cxe2x80x9d, xe2x80x9c{overscore (a)}, {overscore (b)}, {overscore (c)}xe2x80x9d, and xe2x80x9ca, {overscore (b)}xe2x80x9d. That is, the number of logical combinations is three. Similarly, the number of combinations with respect to the variable b is also three. On the other hand, the combinations with respect to the variable c are xe2x80x9ca, b, cxe2x80x9d and xe2x80x9c{overscore (a)}, {overscore (b)} {overscore (c)}xe2x80x9d. That is, the number of combinations is two. When the number of logical combinations is determined with respect to a particular variable, such a combination which does not include one of the variables in the set is also regarded as an allowed combination as long as the combination includes the variable under consideration.
Thus, when the number of combinations with respect to a particular variable is determined for a particular set of variables, there is a possibility that the number of logical combinations varies depending on the variable under consideration. When a variable included in a set having a larger number of combinations is selected as a candidate for a complementary variable, the selection is preferably performed according to the number of combinations with respect to individual variables.
Thus, in the process of grouping the above four product terms, if a and b are selected as complementary variables, then the logic group will become axc2x7bxc2x7(cxc2x7d+cxc2x7e)+axc2x7{overscore (b)}xc2x7(g)+{overscore (a)}xc2x7{overscore (b)}xc2x7({overscore (c)}xc2x7f). This logic group comprises multiple-complementary variables a and b and also three logic functions cxc2x7d+cxc2x7e, g and {overscore (c)}xc2x7f which share the above complementary variables. This logic group, therefore, can be mapped in an efficient fashion to a logic circuit using a 2-stage multiplexer.
In such an optimization comprising: identifying one or more complementary variables from the variables in the product terms; and grouping two or more product terms by the selected complementary variable(s) thereby forming a logic group including the complementary variable(s), the optimization may be performed for either the whole parts of a given logical expression to be realized by a logic circuit or a particular part of the logical expression. Furthermore, the optimization procedure may be performed repeatedly a plurality of cycles so as to enhance the degree of optimization. In the second and subsequent optimization cycles, a particular part is selected and optimized depending on the result of the previous optimization cycle.
If the identification is performed only according to whether the variable is included in a set of variables having a larger number of combinations, there is a possibility that the number of variables at the same level will be too many. In such a case, the frequency of occurrence of a variable in a set of variables having a large number of combinations may be employed as a criterion for identifying a variable as a complementary variable. When a given logical expression is optimized by repeatedly performing the procedures of making a logic group including a complementary variable, the employment of the above selection criterion makes it possible to identify a complementary variable in the second or subsequent optimization processes thereby increasing the possibility of achieving a higher degree of optimization.
In a variable-combination method, which is an embodiment of the present invention, complementary variables are selected according to the criterion in terms of the frequency of occurrence in a set of variables having a great number of combinations.
Furthermore, the present invention also provides a technique of making a logic group including a common variable so as to make it easier to map the logical expression to a circuit using a multiple-input gate in an advantageous fashion.
It is easy to find a common variable included in a particular set of product terms. For example, a common variable can be found by calculating AND of the product terms. However, careful consideration is required to determine which product terms should be grouped together. For example, in the case where a logical expression includes three or more product terms, the common variable may become different depending on which product terms are grouped. For example, in the case of a logical expression axc2x7bxc2x7cxc2x7d+axc2x7bxc2x7cxc2x7e+axc2x7dxc2x7fxc2x7g, if the first and second product terms are grouped, then variables a, b, and c are common variables. On the other hand, variable a and d become common variables if the first and third product terms are grouped. If the second and third product terms are grouped, then variable a becomes a common variable. In the case where the first, second, and third product terms are grouped, variable a becomes a common variable. In general, when an equal number of product terms can be grouped in different manners, it is more desirable to employ a group which includes a larger number of common variables. On the other hand, when product terms can be grouped in different manners so that each group has an equal number of common variables, it is generally desirable to select a group which includes a larger number of product terms. In general, however, the number of common variables decreases with the increase in the number of product terms grouped together.
In embodiments of the present invention, two techniques of optimizing a logical expression by making a logic group including one or more common variables are provided: bottom-up common-variable method and top-down common-variable method.
In a bottom-up common-variable method, product terms are first grouped into groups each including two product terms such that the group includes a larger number of common variables. Then the common variables identified in the above first cycle are regarded as product terms, and the common variables included in these product terms are identified so as to perform a further grouping. Thus, in this technique, the number of grouped product terms increases as the procedure is repeated.
On the other hand, in a top-down common-variable method, product terms are first grouped into 2v groups wherein v is the number of allowed stages of pass transistors used in the logic circuit. For example, when v=2 and there are 32 product terms, common variables are identified for sets of 8 product terms thereby grouping these product terms. In this technique, thus, common variables among a larger number of product terms are identified first. Then, the product terms in each group are further grouped into 2v groups by identifying common variables from a reduced number of product terms. Thus, in this technique, the number of common variables increases as the procedure is repeated.
For example, in a logical expression axc2x7bxc2x7cxc2x7d+axc2x7bxc2x7cxc2x7e+{overscore (a)}xc2x7{overscore (b)}xc2x7{overscore (c)}xc2x7f+axc2x7{overscore (b)}xc2x7g, if the first and second product terms are grouped together and the third and fourth product terms are grouped together so that the resultant groups have common variables a, b and c, and {overscore (b)}, the expression is transformed as axc2x7bxc2x7cxc2x7(d+e)+{overscore (b)}xc2x7({overscore (a)}xc2x7{overscore (c)}xc2x7f+axc2x7g). In the first logic group, logic functions (each is a single variable) d and e share the common variables a, b, and c. While, in the second logic group, logic functions {overscore (a)}xc2x7{overscore (c)}xc2x7f and axc2x7g share the common variable {overscore (b)}. Each of these two logic groups can be mapped in an efficient fashion in which a multiple-input logic gate is advantageously used.
Although either the procedure of making logic groups including complementary variables or the procedure of making logic groups including common variables may only be performed, it is more desirable to perform both procedures so as to obtain greater advantages. If these two techniques are properly coupled together, logical expressions can be optimized in a more desirable fashion in which advantages of both techniques are achieved. That is, it is possible to achieve a reduction in the total number of transistors used in logic circuits and it is also possible to improve the operating speed of the circuits by reducing the number of stages. The grouping of product terms into logic groups including complementary variables may be performed in various manners, and the grouping of product terms into logic groups including common variables may also be performed in various manners. These various procedures may be combined in various orders.
In a common-variable/variable-combination method, which is one embodiment according to the present invention, the above-described common-variable method and the variable-combination method are combined. In this technique, logic groups including common variables are first made according to the common-variable method. Then the common variables which have identified in the above grouping process are regarded as product terms, and variable-combination method is performed on these product terms so as to make logic groups including complementary variables. In this technique in which the common-variable method and the variable-combination method are combined, product terms are first grouped into a form which may be mapped in an efficient fashion using a multiple-input logic gate and which can prevent dispersion of common variables, and then complementary variables are identified so that a multiplexer composed of pass transistors may be advantageously used.
Alternatively, grouping may be performed according to the variable-combination method first, then the logic functions in the obtained groups may be further grouped according to the common-variable method. This technique, which is referred to herein as the variable-combination/common-variable method, is also useful in the optimization. This technique can be further classified into a variable-combination/bottom-up common-variable method and a variable-combination/top-down common-variable method according to whether the common-variable method is performed in a bottom-up fashion or a top-down fashion.
According to another aspect of the present invention, there is provided a method of mapping a combinational logical expression to a logic circuit, comprising: zoning the logic circuit into at least three consecutive positive-, negative- and positive-logic zones; placing a first non-inverting logic gate having at least one input terminal and an output terminal on an input side of the negative-logic zone, a multiplexer having input terminals, at least one control terminal and an output terminal in the negative logic zone, and a second non-inverting logic gate having at least one input terminal and an output terminal on an output side of the negative-logic zone; connecting the input terminals of the multiplexer to non-invertingly input an output signal from the output terminal of the first non-inverting logic gate or to input a direct-input signal; and adjusting logic levels in the logic circuit by inverting the output signal from the first non-inverting logic gate and at least one input signal input to the at least one input terminal of the second non-inverting logic gate.
Preferably, the method further comprises connecting one of the at least one input terminal of the second non-inverting logic gate to non-invertingly input an output signal from the output terminal of the multiplexer, wherein the inverting the input signal to the second non-inverting logic gate includes inverting the direct-input signal input to the input terminal of the multiplexer.
There is also provided a CAD system for mapping a combinational logical expression to a logic circuit, the system comprising: means for zoning the logic circuit into at least three consecutive positive-, negative- and positive-logic zones; means for placing a first non-inverting logic gate having at least one input terminal and an output terminal on an input side of the negative logic zone, a multiplexer having input terminals, at least one control terminal and an output terminal in the negative logic zone, and a second non-inverting logic gate having at least one input terminal and an output terminal on an output side of the negative logic zone; means for connecting the input terminals of the multiplexer to non-invertingly input an output signal from the output terminal of the first multiple-input logic gate or to input a direct-input signal; and means for adjusting logic levels in the logic circuit by inverting the output signal from the first non-inverting logic gate and at least one input signal input to the at least one gate input terminal of the second non-inverting logic gate.
In the case of a logic circuit comprising only pass transistors, inversion in the logic level never occurs. Therefore, in this case, a given logical expression may be mapped to a logic circuit without having to take into account the inversion in the logic level. However, in pass-transistor logic circuits, a reduction in logic swing can occur as signals are passed through pass transistors, and this reduction limits the number of stages of pass transistors which can be connected in series. As a result, it is required that circuit elements such as inverters for restoring the logic swing be inserted in every predetermined number of stages so that the logic swing reduced by the pass transistors is restored to the original level. The inverters cause inversion in the logic level, and therefore it becomes necessary to perform mapping taking into account the inversion in the logic level. To restore the reduction in the logic swing, circuit elements such as buffers which cause no inversion in the logic level may also be employed. However, inverters are more preferable because use of buffers results in an increase in the total number of transistors. When logic circuits are composed of pass transistors and one or more multiple input logic gates, the reduction in logic swing can be restored by the multiple-input logic gates. Also in this case, multiple-input logic gates such as NAND or NOR gates by which signals are inverted are more preferable than those which cause no inversion in the logic level, such as AND or OR gates, from the viewpoint of reduction in the total number of transistors. Therefore, the mapping should be performed taking into account the inversion in the logic level.
One technique of performing mapping taking into account the inversion in the logic level is to first perform mapping without taking into account the inversion in the logic level (preliminary mapping), and then adjust the logic level (logic level adjustment). In the preliminary mapping, a given logical expression is mapped using circuit elements which do not give rise to inversion in the logic level such as buffers, AND gates, or OR gates (herein such types of elements are referred to as xe2x80x9cnon-inverting logic gatesxe2x80x9d). After forming a logic circuit in which at least a major part of the given logical expression is mapped, logic levels are adjusted. In the logic level adjustment, the non-inverting logic gates are replaced by circuit elements which cause inversion in the logic level such as inverters, NAND gates, or NOR gates (herein such types of elements are referred to as xe2x80x9cinverting logic gatesxe2x80x9d). It is not necessary to consider the inversion in logic level in the preliminary mapping process, because no inverting logic gates are used. Therefore, the given logical expression can be mapped in a short time by a simple process. After that, the non-inverting logic gates are replaced by inverting logic gates in the logic level adjustment so that the final logic circuit includes a reduced number of transistors.
In the preliminary mapping, when the output of a non-inverting logic gate is connected to an input terminal of a multiplexer, the connection is made non-invertingly. That is, the connection is made without passing through, for example, an inverting logic gate such as an inverter. Similarly, when the output of a multiplexer is connected to an input terminal of a non-inverting logic gate, the connection is made so that no inversion in the logic level occurs. In addition to the signal from the output terminal of non-inverting logic gate, other input signals such as variables or constants may also be input to the input terminals of a multiplexer without passing through the non-inverting logic gate. Herein such signals are referred to as xe2x80x9cdirect-input signals.xe2x80x9d
In the logic level adjustment, the logic circuit obtained in the primary mapping is divided at the non-inverting logic gates, and positive-logic zones and negative-logic zones are alternately formed. This procedure may also be performed, equivalently, by first forming alternately positive-logic zones and negative-logic zones and then placing non-inverting gates at boundaries between adjacent positive- and negative-logic zones while placing multiplexers in the respective positive- and negative-logic zones thereby mapping the given logical expression therein. In a simplest case, for example, three consecutive positive-, negative- and positive-logic zones are formed, and then non-inverting logic gates are placed on input and output side of the negative-logic zone and a multiplexer is placed in the negative-logic zone. Furthermore, signals output from non-inverting logic gates placed at the input side of the negative-logic zone are inverted, and signals input to non-inverting logic gates placed at the output side of the negative-logic zone are inverted.
Herein, the process of xe2x80x9cinverting signalsxe2x80x9d refers to a procedure performed on a CAD system and does not refer to a process of actually inserting inverters in the circuit. Thus, the non-inverting logic gates are replaced by inverting logic gates. The above process is equivalent to such a process in which inverters are temporarily inserted in the circuit and then each set of a non-inverting gate and one or more inverters is replaced by an equivalent inverting logic gate including a less number of transistors. More specifically, AND and OR gates at the input side of negative-logic zones are replaced by NAND and NOR gates, respectively, and AND and OR gates at the output side of negative-logic zones are replaced by zero-AND gates (=NOR gates) and zero-OR gates (=NAND gates). Buffers at the input and output sides are all replaced by inverters. Furthermore, those signals which are directly input to the input terminals of the multiplexers in the negative-logic zones are also inverted. Thus these signals are transmitted via multiplexers to the input terminals of the logic gates at the output side of the negative-logic zones. As a result, the signals transmitted via multiplexers and input to the logic gates at the output side of the negative-logic zones are also inverted.
In practice, if a given logical expression is directly mapped to a logic circuit, high efficiency and high performance (a small number of transistors included, low power consumption, high operating speed) are not always achieved in the resultant logic circuit. To avoid such the problem, it is desirable to optimize the given logical expression before the mapping so that the logical expression can be mapped to a logic circuit in a highly efficient fashion. That is, as shown in FIG. 7, it is desirable to design the logic circuit as follows. First in step SR12 in FIG. 7, the given logic expression is optimized. Then in step SR14, the optimized logic expression is mapped to a logic circuit in the preliminary mapping. Finally, in step SR16, the logic level is adjusted.
The preliminary mapping process may be performed either in such a manner that the mapping is performed from the lowest-level groups in the logical expression to the highest-level group, or in such a manner that the mapping is performed from the highest-level group to the lowest-level groups. The highest-level group refer to such a group having the strongest influence on the value of the logical expression, and the lowest-level groups refer to such groups having the weakest influence. The highest-level group is mapped nearest to the output of the logic circuit, and the lowest-level groups are mapped nearest to the input of the logic circuit. This means that the mapping is performed either from the input side to the output side of the logic circuit or from the output side to the input side of the logic circuit. To perform the mapping in such the systematic order, it is required that the logical expression to be mapped has a hierarchical structure at least in some part thereof. For example, in the variable-combination method, common-variable method, and common-variable/variable-combination method, as will be described in greater detail later, either one of or both the procedure of grouping the product terms in given logical expression by making logic groups including complementary variables and the procedure of grouping the product terms in the logical expression by making logic groups including common variables are performed repeatedly thereby optimizing the logical expression into a hierarchical structure.
Another method of mapping the logical expression taking into account the inversion of logical levels at inverting logic gates is to take the inversion of the logical level into account from the beginning of the mapping process so that the logical level adjustment is simultaneously made during the mapping process. The advantage of this method is that a logic circuit including inverting logic gates can be formed by a process including a smaller number of steps than can be achieved by the method in which the logic level adjustment is made after the primary mapping process.
The mapping procedure is the same as that performed in the method in which the logic level adjustment is made after the preliminary mapping except that the logic level adjustment is made simultaneously.
More specifically, the circuit is divided at logic gates such that positive-logic zones and negative-logic zones are disposed alternately and inverting logic gates are placed at the boundaries between respective positive-logic and negative-logic zones. For example, when an AND gate is required to map a logic group including a common variable at the input side of a negative-logic zone, a NAND gate is placed there instead of the AND gate so that the output signal is inverted. On the other hand, if an AND gate is required to be mapped at the output side of a negative-logic zone, a zero-AND gate (=NOR gate) is placed there instead of the AND gate. When an OR gate is required to be mapped at the input side of a negative-logic zone, a NOR gate is employed instead of the OR gate. If an OR gate is required to be mapped at the output side of a negative-logic zone, a NAND gate is placed there instead of the OR gate. In the case where a signal is directly input to a negative-logic zone, the signal is inverted.
In the top-down mapping method according to an embodiment of the invention, a logical expression having a hierarchical structure is mapped from the highest-level group to the lowest-level groups taking into account the logic level inversion at inverting logic gates. More specifically, a final-stage of the logic circuit is determined in accordance with the given logical expression to be realized wherein the final-stage of the logic circuit is made in a positive-logic zone if the corresponding logic is represented in a positive-logic form while the final-stage is made in a negative-logic zone if the logic is represented in a negative-logic form. Then positive-logic zones and negative-logic zones are formed alternately whenever an inverting logic gate is placed in the circuit during the mapping from the output side to the input side of the logic circuit. When the highest-level group is mapped, if it has only such logic functions which share one or more complementary variables, a multiplexer with an inverter at the output is placed at the output of the logic circuit. When the highest-level group includes only one logic function including one or more common variables, a NOR gate is placed at the output of the logic circuit if the output of the logic circuit is in the positive-logic form, while a NAND gate is placed if the output of the logic circuit is in the negative-logic form. When the highest-level group includes only one logic function having no common variable, an inverter is placed at the output of the logic circuit. When the highest-level group includes a plurality of independent subservient logic groups, a NAND gate is placed at the output of the logic circuit if the final output is in the positive-logic form while a NOR gate is placed if the final output is in the negative-logic form.
According to another aspect of the present invention, there is provided a method of mapping a logical expression to a logic circuit, the expression comprising a first and a second product term including n and m logic functions, wherein m is greater than n, the method comprising: placing a first multiple-input logic gate having at least n input terminals and an output terminal; connecting the input terminals of the first multiple-input logic gate to directly input the logic functions of the first product term so that the first product term is output from the output terminal of the first multiple-input logic gate; placing a second multiple-input logic gate having less than m input terminals and an output terminal, and an unit multiplexer having a first input terminal, a second input terminal to input a constant, a control terminal and an output terminal; connecting the first input and control terminal of the unit multiplexer to input at least two of the logic functions of the second product term; and connecting the input terminals of the second multiple-input logic gate to input the logic functions of the second product term by inputting the at least two of the logic functions through the output terminal of the unit multiplexer so that the second product term is output from the output terminal of the second multiple-input logic gate.
There is also provided a CAD system for mapping a logical expression to a logic circuit, the expression comprising a first and a second product term including n and m logic functions, wherein m is greater than n, the system comprising: means for placing a first multiple-input logic gate having at least n input terminals and an output terminal; means for connecting the input terminals of the first multiple-input logic gate to directly input the logic functions of the first product term so that the first product term is output from the output terminal of the first multiple-input logic gate; means for placing a second multiple-input logic gate having less than m input terminals and an output terminal, and a first unit multiplexer having a first input terminal, a second input terminal to input a constant, a control terminal and an output terminal; and means for connecting the first input and control terminal of the unit multiplexer to input at least two of the logic functions of the second product term; and means for connecting the input terminals of the second multiple-input logic gate to input the logic functions of the second product term by inputting the at least two of the logic functions through the output terminal of the unit multiplexer so that the second product term is output from the output terminal of the second multiple-input logic gate.
There is further provided a logic circuit for executing a logical operation expressed by a logical expression comprising a first and a second product term including n and m logic functions, wherein m is greater than n, the logic circuit comprising: a first multiple-input logic gate having at least n input terminals and an output terminal, wherein the logic functions of the first product term are input directly to the input terminals of the first multiple-input logic gate to output the first product term from the output terminal of the first multiple-input logic gate; a second multiple-input logic gate having less than m input terminals and an output terminal; and an unit multiplexer having a first input terminal, a second input terminal to input a constant, a control terminal and an output terminal connected to one of the input terminals of the second multiple-input logic gate, wherein the logic functions of the second product term are input to the input terminals of the second multiple-input logic gate by inputting at least two of the logic functions through the first input and the control terminal of the unit multiplexer to output the second product term from the output terminal of the second multiple-input logic gate.
There is also provided an electronic system including a logic circuit for executing a logical operation expressed by a logical expression comprising a first and a second product term including n and m logic functions, wherein m is greater than n, the logic circuit comprising: a first multiple-input logic gate having at least n input terminals and an output terminal, wherein the logic functions of the first product term are input directly to the input terminals of the first multiple-input logic gate to output the first product term from the output terminal of the first multiple-input logic gate; a second multiple-input logic gate having less than m input terminals and an output terminal; and an unit multiplexer having a first input terminal, a second input terminal to input a constant, a control terminal and an output terminal connected to one of the input terminals of the second multiple-input logic gate, wherein the logic functions of the second product term are input to the input terminals of the second multiple-input logic gate by inputting at least two of the logic functions through the first input and the control terminal of the unit multiplexer to output the second product term from the output terminal of the second multiple-input logic gate.
There is also provided a method of executing a logical operation expressed by a logical expression comprising a first and a second product term including n and m logic functions, wherein m is greater than n, the method comprising: inputting the logic functions of the first product term directly to input terminals of a first multiple-input logic gate to output the first product term from an output terminal of the first multiple-input logic gate; inputting at least two of the logic functions of the second product term to a first input and a control terminal of an unit multiplexer having a second input terminal connected to input a constant; and inputting the logic functions of the second product term to input terminals of a second multiple-input logic gate by inputting the at least two of the logic functions through an output terminal of the unit multiplexer to output the second product term from an output terminal of the second multiple-input logic gate.
When a given logical expression is mapped to a logic circuit including pass transistors and multiple-input logic gates either in such a manner that the preliminary mapping is first performed and then the logic level adjustment is made or in such a manner that the logic level adjustment is made during the mapping process, it is desirable to properly combine multiple-input logic gates and pass transistors so that the total number of transistors and the number of stages in the resultant logic circuit are minimized.
In the mapping of the logical expression to the logic circuit, mapping of product terms is common. In the mapping of the lowest-level group, each product term includes only variables. In the mapping of groups other than the lowest-level group, each product term includes one or more variables and one or more logic functions mapped by other logic circuits, or otherwise each product term includes a plurality of logic functions. For example, in the case of a logic group including a common variable, if the sum of the logic functions which share that common variable is regarded as one logic function, then that logic group can be regarded as a product term including that logic function and the common variable. A logic function in the simplest form is a single variable. Therefore, xe2x80x9ca product term including logic functionsxe2x80x9d includes a product of variables.
When such products term are mapped into a logic circuit using pass transistors and multiple-input logic gates, it is desirable to properly combine multiple-input logic gates and pass transistors depending on the number of logic functions included in the product term so that the number of transistors and the number of stages are minimized. For example, if a product term is mapped using only a multiple-input logic gate, it is required that the multiple-input logic gate should have as many input terminals as there are logic functions in the product term. However, the number of transistors included in the multiple-input logic gate increases with the number of input terminals. Furthermore, the number of stages increases and the operating speed decreases with the number of input terminals. To avoid the above problem, it is generally desirable to limit the number of input terminals of the multiple-input logic gate to three or four. If a product term to be mapped includes a greater number of logic functions than the upper limit, a pass transistor is combined with a multiple-input logic gate.
More specifically, the total number of variables or logic functions included in a product term is two or more but less than the maximum allowable number of input terminals of the multiple-input logical gate, a multiple-input logical gate is placed and the logic functions are input to the input terminals thereof. On the other hand, if the total number of logic functions is greater than the maximum allowable number of input terminals of the multiple-input logical gate, a multiple-input logic gate and a pass transistor is combined such that the output of the pass-transistor is connected to an input terminal of the multiple-input logic gate and the input terminal and the control terminal of the pass transistor as well as the input terminals of the multiple-input logic gate are used to receive logic signals corresponding to the logic functions.
In general, it is preferable to employ a combination of pass transistors in a form of a multiplexer rather than a single pass transistor. When an unit multiplexer is used, a constant is input to one of the two input terminals, and the output terminals is connected to one of the input terminal of a multiple-input logical gate. The other input terminals and the control terminal of the unit multiplexer are used to receive logic functions of the product term. That is, it is possible to input two logic functions to the multiple-input logic gate via the unit multiplexers wherein one logic function is input to one input terminal of the multiplexer and another logic function is input to the control terminal of the multiplexer. When a series connection of two unit multiplexers is connected to one input terminal of a multiple-input logic gate, two logic functions are connected to one input terminal and the control terminals, respectively, of the first-stage unit multiplexer so that these two logic functions are input to one input terminal of the second-stage unit multiplexer via the first-stage unit multiplexer. These two logic functions and another logic function input to the control terminal of the second-stage unit multiplexer, thus three logic functions in total, are input to the multiple-input logic gate via the two unit multiplexers. If a large number, within an allowable limit, of multiplexers are connected in series, and each input terminal of a multiple-input logic gate is connected to a similar series connection of unit multiplexers, then it becomes possible to map a product term including a greater number of logic functions.
In other words, when the number of logic functions included in a product term is equal to or less than the maximum allowable number of input terminals of the multiple-input logic gate, all the logic functions are input directly, i.e., without passing through multiplexers, to the input terminals of the multiple-input logic gate. While, when the number of logic functions is larger than the maximum allowable number of input terminals of the multiple-input logic gate, some of the logic functions are input through one or more multiplexers and they are input to the input terminals of the multiple-input logic gate.
In the case where an inverter including a pull-up transistor is used to restore the reduction in the logic swing which occurs when a signal is passed through pass transistors, as disclosed in U. S. patent application Ser. No. 08/716,883 or in the second prior art described earlier, logic functions input through the one or more multiplexers (or, more accurately, a product of the logic functions) is input to the corresponding input terminal of the multiple-input logic gate after the product is inverted by the inverter.
In the case where product terms are mapped in the above-described manner in the preliminary mapping procedure, AND gates are used as the multiple-input logic gates. These AND gates are replaced by NAND or NOR gates in the logic level adjustment after completion of the preliminary mapping. On the other hand, in the case where the logic level adjustment is performed during the mapping, NOR or NAND gates are employed depending on whether the gates are placed at the output side or input side of the negative-logic zones.
In some cases, a logic function included in a product term can be represented by a product of a plurality of variables, a plurality of subservient logic functions, or a combination of variable(s) and subservient logical function(s). In this case, the logic function may first be mapped into a circuit using for example a multiple-input logic gate, and then the product term may be mapped using another multiple-input logic gate in the above-described manner. In this case, the number of unit multiplexers combined with the multiple-input logic gate by which the product term is mapped is determined by the number of logic functions included in the product term wherein the former logic function is counted as one. Alternatively, one or more variables or lower-level logic functions included in such a logic function may be input to the input terminals, respectively, of a multiple-input logic gate by which the product term is mapped. In this case, the number of unit multiplexers combined with the multiple-input logic gate by which the product term is mapped is determined by the total number of logic functions included in the product term wherein all the variables and subservient logic functions included in the former logic function are counted. To reduce the number of stages and the number of multiple-input logic gates connected in series, the latter technique is more preferable than the former technique.
According to another aspect of the invention, there is provided a method of mapping a logical expression to a logic circuit, comprising: placing a multiple-input logic gate having input terminals and an output terminal, and a multiplexer having input terminals, at least one control terminal and an output terminal in the logic circuit; and connecting the input terminals of the multiple-input logic gate to input subservient logic functions to output a product of the subservient logic functions from an output terminal of the multiple-input logic gate, and the input terminals and the at least one control terminal of the multiplexer to input logic functions including the product of the subservient logic functions and at least one complementary variable to output a logic group including the logic functions and the at least one complementary variable shared by the logic functions from the output terminal of the multiplexer.
There is also provided a CAD system for mapping a logical expression to a logic circuit, the system comprising: means for placing a multiple-input logic gate having input terminals and an output terminal, and a multiplexer having input terminals, at least one control terminal and an output terminal in the logic circuit; and means for connecting the input terminals of the multiple-input logic gate to input subservient logic functions to output a product of the subservient logic functions from an output terminal of the multiple-input logic gate, and the input terminals and the at least one control terminal of the multiplexer to input logic functions including the product of the subservient logic functions and at least one complementary variable to output a logic group including the logic functions and the at least one complementary variable shared by the logic functions from the output terminal of the multiplexer.
There is further provided a logic circuit for executing a logical operation, comprising: a multiple-input logic gate having input terminals to input subservient logic functions and an output terminal to output a product of the subservient logic functions; and a multiplexer having input terminals to input logic functions including the product of the subservient logic functions, at least one control terminal to input at least one complementary variable and an output terminal to output a logic group including the logic functions and the at least one complementary variable shared by the logic functions.
There is also provided an electronic system comprising a logic circuit for executing a logical operation, the logic circuit comprising: a multiple-input logic gate having input terminals to input subservient logic functions and an output terminal to output a product of the at least two subservient logic functions; and a multiplexer having input terminals to input logic functions including the product of the subservient logic functions, at least one control terminal to input at least one complementary variable and an output terminal to output a logic group including the logic functions and the at least one complementary variable shared by the logic functions.
There is also provided a method of executing a logical operation, comprising: inputting subservient logic functions to input terminal of a multiple-input logic gate to output a product of the subservient logic functions from an output terminal of the multiple-input logic gate; and inputting logic functions including the product of the subservient logic functions and at least one complementary variable to input terminals and to at least one control terminal of a multiplexer to output a logic group including the logic functions and the at least one complementary variable shared by the logic functions from an output terminal of the multiplexer.
When the given logical expression is mapped to a logic circuit including pass transistors and a multiple-input logic gate, if the logical expression includes a logic group including a complementary variable, a multiplexer formed by combining pass transistors is employed in the mapping, while a multiple-input logic gate is employed if the logical expression includes a product of logic functions, so that the logic expression is mapped to the logic circuit using a smaller number of transistors and a smaller number of stages. Therefore, in the case where the logical expression includes a logic group including a complementary variable, logic functions which share that complementary variable are input to input terminals, respectively, of a multiplexer, and the complementary variable is input to the control terminal of the multiplexer. If the logic group includes multiple-complementary variables, a multi-stage multiplexer is employed. If a part of or all of the logic functions which share the complementary variable are each a product of subservient logic functions, such the logic functions are first mapped using multiple-input logic gates and then input to the input terminals of a multiplexer. That is, the subservient logic functions are input to input terminals of a multiple-input logic gate so that the logic function including these subservient logic functions is output from the output terminal of the multiple-input logic gate. Depending on the number of subservient logical functions included in the product term, a certain number of unit multiplexers whose one input is maintained at a constant logical value are added.
According to another aspect of the invention, there is provided a method of mapping a logical expression to a logic circuit, comprising: placing a multiplexer having input terminals, at least one control terminal and an output terminal, and a multiple-input logic gate having a first input terminal, at least one second input terminal and an output terminal in the logic circuit; and connecting the input terminals and the at least one control terminal of the multiplexer to input subservient logic functions and at least one complementary variable to output a subservient logic group including the subservient logic functions and at least one complementary variable shared by the subservient logic functions from the output terminal of the multiplexer, and the first input terminal and the at least one second input terminal of the multiple-input logic gate to input the subservient logic group and at least one common variable to output a logic group comprising a product of the at least one common variable and the subservient logic group from the output terminal of the multiple-input logic gate.
There is also provided a CAD system for mapping a logical expression to a logic circuit, the system comprising: means for placing a multiplexer having input terminals, at least one control terminal and an output terminal, and a multiple-input logic gate having a first input terminal, at least one second input terminal and an output terminal in the logic circuit; and means for connecting the input terminals and the at least one control terminal of the multiplexer to input subservient logic functions and at least one complementary variable to output a subservient logic group including the subservient logic functions and the at least one complementary variable shared by the subservient logic functions from the output terminal of the multiplexer, and the first input terminal and the at least one second input terminal of the multiple-input logic gate to input the subservient logic group and at least one common variable to output a logic group comprising a product of the at least one common variable and the subservient logic group from the output terminal of the multiple-input logic gate.
There is further provided a logic circuit for executing a logical operation, comprising: a multiplexer having input terminals to input subservient logic functions, at least one control terminal to input at least one complementary variable and an output terminal to output a subservient logic group including the subservient logic functions and the at least one complementary variable shared by the subservient logic functions; and a multiple-input logic gate having a first input terminal to input the subservient logic group and at least one second input terminal to input at least one common variable and an output terminal to output a logic group comprising a product of the subservient logic group and the at least one common variable.
There is also provided an electronic system comprising a logic circuit for executing a logical operation, the logic circuit comprising: a multiplexer having input terminals to input subservient logic functions, at least one control terminal to input at least one complementary variable and an output terminal to output a subservient logic group including the subservient logic functions and the at least one complementary variable shared by the subservient logic functions; and a multiple-input logic gate having a first input terminal to input the subservient logic group and at least one second input terminal to input at least one common variable and an output terminal to output a logic group comprising a product of the subservient logic group and the at least one common variable.
There is also provided a method of executing a logical operation, comprising: inputting subservient logic functions and at least one complementary variable to input terminals and to at least one control terminal of a multiplexer to output a subservient logic group including the subservient logic functions and the at least one complementary variable shared by the subservient logic functions from an output terminal of the multiplexer; and inputting the subservient logic group and at least one common variable to a first input terminal and to at least one second input terminal of a multiple-input logic gate to output a logic group comprising a product of the at least one common variable and the subservient logic group from the output terminal of the multiple-input logic gate.
In the case where the logical expression to be mapped includes a logic group including a common variable, the common variable and a sum of logic functions which share the common variable are input to the input terminals of a multiple-input logic gate. If the sum of the logic functions sharing the common variable is a subservient logic group including a complementary variable, the subservient logic group is first mapped using a multiplexer and then is input to the multiple-input logic gate. That is, the subservient logic functions which share the complementary variable is input to the input terminals of the multiplexer and the complementary variable is input to the control terminal of the multiplexer so that the subservient logic group is output from the output terminal of the multiplexer. The subservient logic group mapped in the above-described manner and the common variable are input to the input terminals of the multiple-input logic gate. Depending on the number of common variables, a required number of unit multiplexers whose one input terminal is maintained at a constant logic value are added. If the subservient logic group is a logic group including multiple-complementary variables, a multi-stage multiplexers is employed.
In the case where an inverter including a pull-up transistor is used to restore the reduction in the logic swing which occurs when a signal is passed through pass transistors, the subservient logic group output from the output terminal of the multiplexer is input to the input terminal of the multiple-input logic gate after the subservient logic group is inverted by the inverter.
If a part of or all of the subservient logic functions which share the complementary variable are each a product of second-subservient logic functions, such the subservient logic functions are first mapped using another multiple-input logic gate and then input to the input terminals of a multiplexer.
According to still another aspect of the invention, there is provided a method of mapping a logical expression to a logic circuit, comprising: placing a first-type multiple-input logic gate having input terminals and an output terminal, a multiplexer having input terminals, at least one control terminal and an output terminal, and a second-type multiple-input logic gate having input terminals and an output terminal in the logic circuit; and non-invertingly connecting one of the input terminals of the multiplexer to the output terminal of the first-type multiple-input logic gate, and one of the input terminals of the second-type multiple-input logic gate to the output terminal of the multiplexer, wherein the first-type multiple-input logic gate is one of a NAND and a NOR gate and the second-type multiple-input logic gate is the other one of a NAND and a NOR gate.
Preferably, the method further comprises: connecting the input terminals of the first-type multiple-input logic gate to input second-subservient logic functions to output a product of the second-subservient logic functions from the output terminal of the first-type multiple-input logic gate, the input terminals and the at least one control terminal of the multiplexer to input subservient logic functions including the product of the second-subservient logic functions and at least one complementary variable to output a subservient logic group including the subservient logic functions and the at least one complementary variable shared by the subservient logic functions from the output terminal of the multiplexer, and the input terminals of the second-type multiple-input logic gate to input logic functions including the subservient logic group to output a logic group comprising a product of the logic functions from the output terminal of the second-type multiple-input logic gate.
There is also provided a CAD system for mapping a logical expression to a logic circuit, comprising: means for placing a first-type multiple-input logic gate having input terminals and an output terminal, a multiplexer having input terminals, at least one control terminal and an output terminal, and a second-type multiple-input logic gate having input terminals and an output terminal in the logic circuit; and means for non-invertingly connecting one of the input terminals of the multiplexer to the output terminal of the first-type multiple-input logic gate, and one of the input terminals of the second-type multiple-input logic gate to the output terminal of the multiplexer, wherein the first-type multiple-input logic gate is one of a NAND and a NOR gate and the second-type multiple-input logic gate is the other one of a NAND and a NOR gate.
There is further provided a logic circuit for executing a logical operation, comprising: a first type multiple-input logic gate having input terminals and an output terminal; a multiplexer having input terminals one of which being non-invertingly connected to the output terminal of the first type multiple-input logic gate, at least one control terminal and an output terminal; and a second-type multiple-input logic gate having input terminals one of which being non-invertingly connected to the output terminal of the multiplexer, and an output terminal, wherein the first-type multiple-input logic gate is one of a NAND and a NOR gate and the second-type multiple-input logic gate is the other one of a NAND and a NOR gate.
Preferably, the input terminals of the first-type multiple-input logic gate are connected to input second-subservient logic functions so that a product of the second-subservient logic functions is output from the output terminal of the first-type multiple-input logic gate; the input terminals and the at least one control terminal of the multiplexer are connected to input subservient logic functions including the product of the second-subservient logic functions and at least one complementary variable so that a subservient logic group including the subservient logic functions and the at least one complementary variable shared by the subservient logic functions is output from the output terminal of the multiplexer; and the input terminals of the second-type multiple-input logic gate is connected to input logic functions including the subservient logic group so that a logic group comprising a product of the logic functions is output from the output terminal of the second-type multiple-input logic gate.
There is also provided an electronic system comprising a logic circuit for executing a logical operation, the logic circuit comprising: a first type multiple-input logic gate having input terminals and an output terminal; a multiplexer having input terminals one of which being non-invertingly connected to the output terminal of the first type multiple-input logic gate, at least one control terminal and an output terminal; and a second-type multiple-input logic gate having input terminals one of which being non-invertingly connected to the output terminal of the multiplexer, and an output terminal, wherein the first-type multiple-input logic gate is one of a NAND and a NOR gate and the second-type multiple-input logic gate is the other one of a NAND and a NOR gate.
There is also provided a method of executing a logical operation, comprising: inputting second-subservient logic functions to input terminals of a first-type multiple-input logic gate to output a product of the second-subservient logic functions from an output terminal of the first-type multiple-input logic gate; inputting subservient logic functions and at least one complementary variable to input terminals and to at least one control terminal of a multiplexer including non-invertingly inputting the product of the second-subservient logic functions as one of the subservient logic functions to output a subservient logic group including the subservient logic functions and the at least one complementary variable shared by the subservient logic functions from an output terminal of the multiplexer; and inputting logic functions to input terminals of a second-type multiple-input logic gate including non-invertingly inputting the subservient logic group as one of the logic functions to output a logic group comprising a product of the logic functions from an output terminal of the second-type multiple-input logic gate, wherein the first-type multiple-input logic gate is one of a NAND and a NOR gate and the second-type multiple-input logic gate is the other one of a NAND and a NOR gate.
As an example, let us assume that the logical expression includes a logic group comprising a product of two or more logic functions, and that one of the logic functions is a subservient logic group including a complementary variable and subservient logic functions which share that complementary variable, and that a part of or all of the subservient logic functions are each a product of second-subservient logic functions. If such the logical expression is mapped to a logic circuit either by means of first performing a preliminary mapping and then performing a logic level adjustment or by means of simultaneously performing a mapping and a logic level adjustment, the resultant logic circuit includes a first-type multiple-input logic gate located at the input side, a multiplexer whose one input terminal is connected to the output terminal of the first-type multiple-input logic gate, and a second-type multiple-input logic gate whose one input terminal is connected to the output terminal of the multiplexer. One of the first- and second-type multiple-input logic gates is a NAND gate and the other is a NOR gate. Which multiple-input logic is a NAND gate or a NOR gate is determined depending on whether the circuit area between these multiple-input logic gates is a positive-logic zone or a negative-logic zone. In this logic circuit, the connection between the output terminal of the first-type multiple-input logic gate and the one input terminal of the multiplexer and also the connection between the output terminal of the multiplexer and the one input terminal of the second-type multiple-input logic gate are made non-invertingly, i.e., the connections are made such that no logic inversion occurs.
The first-type multiple-input logic gate is used to input the second-subservient logic functions at its input terminals and to output from its output terminal the product of the second-subservient logic functions. On the other hand, the multiplexer is used to input the subservient logic functions at its input terminals and also the complementary variable at its control terminal, and to output from its output terminal the subservient logic group including the complementary variable and the subservient logic functions which share that complementary variable. The second-type multiple-input logic gate is used to input the two or more logic functions at its input terminals and to output from its output terminal the logic group comprising the product of those two or more logic functions.
The logic circuit constructed in the above-described manner has the following advantages. First, in this technique, a logic group including a complementary variable is mapped to a multiple-input logic gate and a product of a plurality of logic functions included in the logic group is mapped to a multiple-input logic gate. This makes it possible to realize a logic circuit with a smaller number of transistors and a smaller number of stages taking the advantages of both the pass transistors and the multiple-input logic gates. Furthermore, the use of a NAND or NOR gate, which are an inverting logic gate, as the multiple-input logic gate also allows a reduction in the number of transistors.
In some cases, one of logic functions included in the logic group can be one or more common variables. Depending on the number of common variables, a certain number of unit multiplexers whose one input terminal is maintained at a fixed logic level may also be used in combination of the second-type multiple-input logic gate.
In the case where two or more logic functions included in the logic group are each a subservient logic group including a complementary variable, each subservient logic group may be mapped using one multiplexer.
Let us further assume that one of the second-subservient logic functions is a second-subservient logic group including of a subservient complementary variable and a third-subservient logic functions which share the subservient complementary variable and furthermore a part of or all of the third-subservient logic functions are each comprising a product of fourth-subservient logic functions. In such the case, the second-subservient logic group may be mapped into a logic circuit including a second second-type multiple-input logic gate located at the input side, a second multiplexer whose one input terminal is connected to the output terminal of the second second-type multiple-input logic gate. The second second-type multiple-input logic gate is used to input the fourth-subservient logic functions at its input terminals and to output from its output terminal the third-subservient logic function. The second multiplexer is used to input the third-subservient logic functions at its input terminals and also the subservient complementary variable at its control terminal and to output from its output terminal the second-subservient logic group. The second-subservient logic group thus mapped is then input to an input terminal of the first-type multiple-input logic gate as one of the second-subservient logic functions. The connection between the output terminal of the second second-type multiple-input logic gate and the one input terminal of the second multiplexer and the connection between the output terminal of the second multiplexer and the one input terminal of the first-type multiple-input logic gate are made non-invertingly.